package Hash.Medium;

public class LC2352 {
    /**
     * 这个解法的主要思路是为行/列求哈希，跳过哈希不同的行/列的比较，以降低时间复杂度
     * 官方的题解直接将行作为了哈希的键，构造了一个List<Integer>到Integer的Map（后一个Integer是该行出现的次数）
     */
    public int equalPairs(int[][] grid) {
        int N = grid.length;
        int[] rowHashes = new int[N], colHashes = new int[N];

        // 哈希函数计算：加减交错
        for (int i = 0; i < N; i++) {
            int rowHash = 0, colHash = 0;
            for (int j = 0; j < N; j++) {
                if (j % 2 == 0) {
                    rowHash += grid[i][j];
                    colHash += grid[j][i];
                }
                else {
                    rowHash -= grid[i][j];
                    colHash -= grid[j][i];
                }
            }
            rowHashes[i] = rowHash;
            colHashes[i] = colHash;
        }

        int nPairs = 0;
        for (int row = 0; row < N; row++) {
            for (int col = 0; col < N; col++) {
                if (rowHashes[row] != colHashes[col]) continue;
                // 检查第row行和第col列是否相等
                boolean flag = true;
                for (int i = 0; i < N; i++) {
                    if (grid[row][i] != grid[i][col]) {
                        flag = false;
                        break;
                    }
                }
                if (flag) nPairs++;
            }
        }

        return nPairs;
    }
}
